{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Minimum Absolute Difference in BST"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #tree #depth-first-search #breadth-first-search #binary-search-tree #binary-tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #树 #深度优先搜索 #广度优先搜索 #二叉搜索树 #二叉树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: getMinimumDifference"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #二叉搜索树的最小绝对差"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个二叉搜索树的根节点 <code>root</code> ，返回 <strong>树中任意两不同节点值之间的最小差值</strong> 。</p>\n",
    "\n",
    "<p>差值是一个正数，其数值等于两值之差的绝对值。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/02/05/bst1.jpg\" style=\"width: 292px; height: 301px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>root = [4,2,6,1,3]\n",
    "<strong>输出：</strong>1\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/02/05/bst2.jpg\" style=\"width: 282px; height: 301px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>root = [1,0,48,null,null,12,49]\n",
    "<strong>输出：</strong>1\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>树中节点的数目范围是 <code>[2, 10<sup>4</sup>]</code></li>\n",
    "\t<li><code>0 &lt;= Node.val &lt;= 10<sup>5</sup></code></li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>注意：</strong>本题与 783 <a href=\"https://leetcode-cn.com/problems/minimum-distance-between-bst-nodes/\">https://leetcode-cn.com/problems/minimum-distance-between-bst-nodes/</a> 相同</p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [minimum-absolute-difference-in-bst](https://leetcode.cn/problems/minimum-absolute-difference-in-bst/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [minimum-absolute-difference-in-bst](https://leetcode.cn/problems/minimum-absolute-difference-in-bst/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[4,2,6,1,3]', '[1,0,48,null,null,12,49]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def getMinimumDifference(self, root):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        prev = None\n",
    "        ans = sys.maxsize \n",
    "        def recur(root):\n",
    "            nonlocal prev\n",
    "            nonlocal ans\n",
    "            if not root:\n",
    "                return \n",
    "            recur(root.left)\n",
    "            if prev:\n",
    "                ans =min(ans, root.val - prev.val)\n",
    "            prev=root\n",
    "            recur(root.right)\n",
    "        recur(root)\n",
    "        return ans        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def getMinimumDifference(self, root):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        stack = []\n",
    "        prev = None\n",
    "        cur = root\n",
    "        res = 0x7fffffff\n",
    "        while cur or len(stack) > 0:\n",
    "            if cur:\n",
    "                stack.append(cur)\n",
    "                cur = cur.left\n",
    "            else:\n",
    "                cur = stack.pop()\n",
    "                if prev:\n",
    "                    res = min(cur.val - prev.val, res)\n",
    "                prev = cur\n",
    "                cur = cur.right\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def getMinimumDifference(self, root):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        L = []\n",
    "        def dfs(node):\n",
    "            if node.left: dfs(node.left)\n",
    "            L.append(node.val)\n",
    "            if node.right: dfs(node.right)\n",
    "        dfs(root)\n",
    "        return min(abs(a-b) for a,b in zip(L,L[1:]))\n",
    "                \n",
    "                \n",
    "                \n",
    "                \n",
    "                \n",
    "                \n",
    "                \n",
    "                \n",
    "                \n",
    "                \n",
    "                \n",
    "                \n",
    "#                 def getMinimumDifference(self, root):\n",
    "#         L = []\n",
    "#         def dfs(node):\n",
    "#             if node.left: dfs(node.left)\n",
    "#             L.append(node.val)\n",
    "#             if node.right: dfs(node.right)\n",
    "#         dfs(root)\n",
    "#         return min(abs(a - b) for a, b in zip(L, L[1:]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def getMinimumDifference(self, root):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        result = []\n",
    "        mindiff = float('inf')\n",
    "        self.inorder(root,result)\n",
    "        for i in range(len(result)-1):\n",
    "            mindiff = min(mindiff,result[i+1]-result[i])\n",
    "        return mindiff\n",
    "    def inorder(self,root,result):\n",
    "        if root ==  None:\n",
    "            return\n",
    "        self.inorder(root.left,result)\n",
    "        result.append(root.val)\n",
    "        self.inorder(root.right,result)\n",
    "        \n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def getMinimumDifference(self, root):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        node_list=self.inorder(root).split(',')\n",
    "        res=float('inf')\n",
    "        for i in range(len(node_list)-2):\n",
    "            if node_list[i]:\n",
    "                res=min(res,abs(int(node_list[i])-int(node_list[i+1])))\n",
    "        return res\n",
    "    \n",
    "    def inorder(self,root):\n",
    "        if root:\n",
    "            return self.inorder(root.left)+str(root.val)+','+self.inorder(root.right)\n",
    "        else:\n",
    "            return ''\n",
    "            \n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def getMinimumDifference(self, root: TreeNode) -> int:\n",
    "        \n",
    "        result = []\n",
    "        def midsearch(root):\n",
    "            if root == None:\n",
    "                return\n",
    "            if root.left:\n",
    "                midsearch(root.left)\n",
    "            result.append(root.val)\n",
    "            if root.right:\n",
    "                midsearch(root.right)\n",
    "        midsearch(root)\n",
    "        \n",
    "        if len(result) < 2:\n",
    "            return 0\n",
    "        for i in range(1,len(result)):\n",
    "            result[i-1] = abs(result[i]-result[i-1])\n",
    "        return min(result[:-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getMinimumDifference(self, root):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        gen = self.inorder(root)\n",
    "        x= next(gen)\n",
    "        last = next(gen)\n",
    "        mn = last -x\n",
    "        for i in gen:\n",
    "            print(i)\n",
    "            mn =min(mn,i-last)\n",
    "            last = i\n",
    "        return mn\n",
    "    def inorder(self,root):\n",
    "        if root.left: yield from self.inorder(root.left)\n",
    "        yield root.val\n",
    "        if root.right: yield from self.inorder(root.right)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "import queue\n",
    "\n",
    "class Solution:\n",
    "    def getMinimumDifference(self, root):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        node=root\n",
    "        q=queue.Queue(10000)\n",
    "        q.put_nowait(node)\n",
    "        least=2**32\n",
    "        while not q.empty():\n",
    "            # print('dequeue')\n",
    "            temp=q.get_nowait()\n",
    "            if temp.left:\n",
    "                # print('enqueue')\n",
    "                q.put_nowait(temp.left)\n",
    "            if temp.right:\n",
    "                # print('enqueue')\n",
    "                q.put_nowait(temp.right)\n",
    "                \n",
    "            # start to find left minimum\n",
    "            templ,tempr=temp,temp\n",
    "            \n",
    "            if templ.left:\n",
    "                c1=templ.val\n",
    "                templ = templ.left\n",
    "                c2=-2**32\n",
    "                while templ:\n",
    "                    c2=templ.val\n",
    "                    templ = templ.right\n",
    "                    pass\n",
    "                if least>c1-c2:\n",
    "                    print('c1-c2',c1,c2)\n",
    "                    least=c1-c2\n",
    "            if tempr.right:\n",
    "                c1=tempr.val\n",
    "                tempr = tempr.right\n",
    "                c2 = -2 ** 32\n",
    "                while tempr:\n",
    "                    c2 = tempr.val\n",
    "                    tempr = tempr.left\n",
    "                    pass\n",
    "                if least > c2-c1:\n",
    "                    print('c2-c1',c2,c1)\n",
    "                    least = c2-c1\n",
    "        return least\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def getMinimumDifference(self, root):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        \n",
    "        res = self.tree(root)\n",
    "        \n",
    "        res.sort()\n",
    "        \n",
    "        if len(res) == 1:\n",
    "            return\n",
    "        i = 0\n",
    "        dif = []\n",
    "        while i <= len(res)-2:\n",
    "            if dif == []:\n",
    "                dif.append(abs(res[i]-res[i+1]))  \n",
    "            print(dif)\n",
    "            if dif[0] == 0:\n",
    "                return 0\n",
    "            if dif[0] > abs(res[i] - res[i+1]):\n",
    "                dif[0] = abs(res[i] - res[i+1])\n",
    "                \n",
    "            i +=1\n",
    "            \n",
    "        return dif[0]\n",
    "                \n",
    "        \n",
    "        \n",
    "        \n",
    "    def tree(self,root):\n",
    "        \n",
    "        res = []\n",
    "        \n",
    "        if root == None:\n",
    "            \n",
    "            return res\n",
    "        \n",
    "        else:\n",
    "            \n",
    "            res.append(root.val)\n",
    "            \n",
    "        left = self.tree(root.left)\n",
    "        \n",
    "        right = self.tree(root.right)\n",
    "        \n",
    "        res += left + right\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "# 誤寫成兩相鄰的了\n",
    "# class Solution:\n",
    "#     def getMinimumDifference(self, root: TreeNode) -> int:\n",
    "#         min_diff = float('inf')\n",
    "\n",
    "#         def dfs(node, pre_val):\n",
    "#             nonlocal min_diff\n",
    "#             if node == None:\n",
    "#                 return\n",
    "\n",
    "#             if pre_val != None:\n",
    "#                 current_diff = abs(pre_val - node.val)\n",
    "#                 if current_diff < min_diff:\n",
    "#                     min_diff = current_diff\n",
    "#             dfs(node.left, node.val)\n",
    "#             dfs(node.right, node.val)\n",
    "\n",
    "#         dfs(root, None)\n",
    "#         return min_diff\n",
    "\n",
    "class Solution:\n",
    "    def getMinimumDifference(self, root: TreeNode) -> int:\n",
    "        node_values = []\n",
    "\n",
    "        def dfs(node):\n",
    "            if node == None:\n",
    "                return\n",
    "            dfs(node.left)\n",
    "            node_values.append(node.val)\n",
    "            dfs(node.right)\n",
    "\n",
    "        dfs(root)\n",
    "\n",
    "        # node_values.sort()\n",
    "        min_diff = float('inf')\n",
    "        for i in range(1, len(node_values)):\n",
    "            diff = node_values[i] - node_values[i-1]\n",
    "            if diff < min_diff:\n",
    "                min_diff = diff\n",
    "        return min_diff"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def getMinimumDifference(self, root: TreeNode) -> int:\n",
    "        seq = self.orderedSeq(root)\n",
    "        res = 0xffffffff        \n",
    "        for i in range(1, len(seq)):\n",
    "            res = min(res, abs(seq[i] - seq[i - 1]))\n",
    "        return res\n",
    "    \n",
    "    def orderedSeq(self, root):\n",
    "        if not root:\n",
    "            return []\n",
    "        return self.orderedSeq(root.left) + [root.val] + self.orderedSeq(root.right)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def getMinimumDifference(self, root: TreeNode) -> int:\n",
    "        self.res=float(\"inf\")\n",
    "        self.pre=None\n",
    "        def LDR(root):\n",
    "            if not root:\n",
    "                return\n",
    "            LDR(root.left)\n",
    "            if self.pre==None:\n",
    "                self.pre=root.val\n",
    "            else:\n",
    "                self.res=min(abs(root.val-self.pre),self.res)\n",
    "                self.pre=root.val\n",
    "            LDR(root.right)\n",
    "\n",
    "        LDR(root)\n",
    "        return self.res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.res = float('inf')\n",
    "        self.temp = -1\n",
    "    def dfs(self,root):\n",
    "        if not root:\n",
    "            return    \n",
    "        \n",
    "        self.dfs(root.left)\n",
    "\n",
    "        if self.temp == -1:\n",
    "           self.temp = root.val\n",
    "        else:\n",
    "            right = abs(root.val-self.temp)\n",
    "            self.res = min(self.res,right)\n",
    "            self.temp = root.val\n",
    "        self.dfs(root.right)\n",
    "        \n",
    "    def getMinimumDifference(self, root: TreeNode) -> int:\n",
    "      \n",
    "        self.dfs(root)\n",
    "        return self.res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def getMinimumDifference(self, root: TreeNode) -> int:\n",
    "        def dps(root:TreeNode,minRst:int,lastval)->(int,int):\n",
    "            if not root:return minRst,lastval\n",
    "            minRst,lastval = dps(root.left,minRst,lastval)\n",
    "            if lastval is not None:\n",
    "                minRst = min(minRst,abs(root.val-lastval))\n",
    "            return dps(root.right,minRst,root.val)\n",
    "        return dps(root,float('inf'),None)[0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def getMinimumDifference(self, root: TreeNode) -> int:\n",
    "        inorder = self.inOrder(root)\n",
    "        ans = float('inf')\n",
    "        for i in range(1, len(inorder)):\n",
    "            ans = min(ans, inorder[i]-inorder[i-1])\n",
    "        return ans\n",
    "\n",
    "\n",
    "    def inOrder(self, root):\n",
    "        ans = []\n",
    "        if root:\n",
    "            ans += self.inOrder(root.left)\n",
    "            ans.append(root.val)\n",
    "            ans += self.inOrder(root.right)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def getMinimumDifference(self, root: TreeNode) -> int:\n",
    "        # dfs 深度优先中序遍历\n",
    "        stack = []\n",
    "        pre = None\n",
    "        mini = float('inf')\n",
    "        while stack or root:\n",
    "            while root:\n",
    "                stack.append(root)\n",
    "                root = root.left\n",
    "            node = stack.pop()\n",
    "            if pre:\n",
    "                mini = min(mini, node.val - pre.val)\n",
    "            pre = node\n",
    "            root = node.right\n",
    "        return mini"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "\n",
    "\n",
    "\n",
    "    def getMinimumDifference(self, root: TreeNode) -> int:\n",
    "        def inOrder(root:TreeNode)->list:\n",
    "            if root==None:\n",
    "                return []\n",
    "            return inOrder(root.left)+[root.val]+inOrder(root.right)\n",
    "        nums=inOrder(root)\n",
    "        pre=0\n",
    "        cur=1\n",
    "        minNum=abs(nums[pre]-nums[cur])\n",
    "        while (cur<len(nums)):\n",
    "            temp=abs(nums[pre]-nums[cur])\n",
    "            minNum=min(minNum,temp)\n",
    "            cur+=1\n",
    "            pre+=1\n",
    "        return minNum\n",
    "    \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x:\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def getMinimumDifference(self, root: TreeNode) -> int:\n",
    "        allnode=set()\n",
    "\n",
    "        def helper(node):\n",
    "            if not node:return\n",
    "            allnode.add(node.val)\n",
    "            helper(node.left)\n",
    "            helper(node.right)\n",
    "\n",
    "        helper(root)\n",
    "        allnode=list(allnode)\n",
    "        allnode.sort()\n",
    "        # print(allnode)\n",
    "\n",
    "        # mindiff=float('inf')\n",
    "        # for i in range(1,len(allnode)):\n",
    "        #     mindiff=min(mindiff,allnode[i]-allnode[i-1])\n",
    "        # return mindiff\n",
    "\n",
    "        return min(allnode[i]-allnode[i-1] for i in range(1,len(allnode)))\n",
    "       \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def getMinimumDifference(self, root: TreeNode) -> int:\n",
    "        allNumbs = []\n",
    "        def dfs(node):\n",
    "            if node:\n",
    "                allNumbs.append(node.val)\n",
    "                dfs(node.left)\n",
    "                dfs(node.right)\n",
    "            else:\n",
    "                return\n",
    "        dfs(root)\n",
    "        print(allNumbs)\n",
    "        twoNumbsSub = set()\n",
    "        n = len(allNumbs)\n",
    "        for i in range(0,n - 1):\n",
    "            for j in range(i + 1,n):\n",
    "                twoNumbsSub.add(abs(allNumbs[i]  - allNumbs[j]))\n",
    "        \n",
    "        return min(twoNumbsSub)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def getMinimumDifference(self, root: TreeNode) -> int:\n",
    "        lst = []\n",
    "        self.in_trans(root, lst)\n",
    "        pre, _next = 0, 1\n",
    "        min_diff = abs(lst[0] - lst[1])\n",
    "        while _next < len(lst):\n",
    "            pre_val, next_val = lst[pre], lst[_next]\n",
    "            diff = abs(next_val-pre_val)\n",
    "            if diff < min_diff:\n",
    "                min_diff = diff\n",
    "            pre = _next \n",
    "            _next += 1\n",
    "        return min_diff\n",
    "    \n",
    "    def in_trans(self, root: TreeNode, lst: list):\n",
    "        if not root:\n",
    "            return None\n",
    "        self.in_trans(root.left, lst)\n",
    "        lst.append(root.val)\n",
    "        self.in_trans(root.right, lst)\n",
    "        return lst"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def getMinimumDifference(self, root: TreeNode) -> int:\n",
    "        stack = []\n",
    "        cur = root\n",
    "        pre = None\n",
    "        result = float('inf')\n",
    "\n",
    "        while cur or stack:\n",
    "            if cur:\n",
    "                stack.append(cur)\n",
    "                cur = cur.left\n",
    "            else:\n",
    "                cur = stack.pop()\n",
    "                if pre:\n",
    "                    result = min(result, cur.val - pre.val)\n",
    "                pre = cur\n",
    "                cur = cur.right\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\r\n",
    "# class TreeNode:\r\n",
    "#     def __init__(self, val=0, left=None, right=None):\r\n",
    "#         self.val = val\r\n",
    "#         self.left = left\r\n",
    "#         self.right = right\r\n",
    "class Solution:\r\n",
    "    def getMinimumDifference(self, root: Optional[TreeNode]) -> int:\r\n",
    "        prev=float('-inf')\r\n",
    "        mini=float('inf')\r\n",
    "        def searcher(root):\r\n",
    "            if not root: return\r\n",
    "            nonlocal prev,mini\r\n",
    "            searcher(root.left)\r\n",
    "            mini=min(root.val-prev,mini)\r\n",
    "            prev=root.val\r\n",
    "            searcher(root.right)\r\n",
    "        searcher(root)\r\n",
    "        return mini"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def getMinimumDifference(self,root):\n",
    "        result=[]\n",
    "        record=[]\n",
    "        self.zhongxu(root,result)\n",
    "        for i in range(len(result)-1):\n",
    "            record.append(abs(result[i+1]-result[i]))\n",
    "        return min(record)\n",
    "\n",
    "    def zhongxu(self,root,result):\n",
    "        if not root:\n",
    "            return None\n",
    "        self.zhongxu(root.left,result)\n",
    "        result.append(root.val)\n",
    "        self.zhongxu(root.right,result)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def getMinimumDifference(self, root: Optional[TreeNode]) -> int:\n",
    "        st = []\n",
    "        p = root\n",
    "        pre = -float('inf')\n",
    "        min_val = float('inf')\n",
    "        while p is not None or st:\n",
    "            while p is not None:\n",
    "                st.append(p)\n",
    "                p = p.left\n",
    "            p = st.pop()\n",
    "            cur = p.val\n",
    "            if cur - pre < min_val:\n",
    "                min_val = cur - pre\n",
    "            pre = cur\n",
    "            p = p.right\n",
    "        return min_val"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def getlist(self,root,a):\n",
    "        if root.left:\n",
    "            a=self.getlist(root.left,a)\n",
    "        a.append(root.val)\n",
    "        if root.right:\n",
    "            a=self.getlist(root.right,a)\n",
    "        return a\n",
    "\n",
    "    def getMinimumDifference(self, root: Optional[TreeNode]) -> int:\n",
    "        a=[]\n",
    "        a=self.getlist(root,a)\n",
    "        mindiff=100000\n",
    "        for i in range(len(a)-1):\n",
    "            if a[i+1]-a[i] < mindiff:\n",
    "                mindiff=a[i+1]-a[i]\n",
    "        return mindiff\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.arr = []\n",
    "        \n",
    "\n",
    "    def getMinimumDifference(self, root: Optional[TreeNode]) -> int:\n",
    "        res = float('inf') \n",
    "        self.dfs(root)\n",
    "        for i in range(1, len(self.arr)):\n",
    "            res = min(res, self.arr[i] - self.arr[i-1])\n",
    "\n",
    "        return res \n",
    "\n",
    "    def dfs(self, root):\n",
    "        if not root: return \n",
    "\n",
    "        if root.left: self.dfs(root.left)\n",
    "        self.arr.append(root.val)\n",
    "        if root.right: self.dfs(root.right)\n",
    "\n",
    "\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.pre=None\n",
    "        self.result=0\n",
    "    def trverse(self,cur):\n",
    "        stack=[cur]\n",
    "        listt=[]\n",
    "        while stack:\n",
    "            r=stack.pop()\n",
    "            if r:\n",
    "                if r.right:\n",
    "                    stack.append(r.right)\n",
    "                stack.append(r)\n",
    "                stack.append(None)\n",
    "                if r.left:\n",
    "                    stack.append(r.left)\n",
    "            else:\n",
    "                r=stack.pop()\n",
    "                listt.append(r.val)\n",
    "        min_result=float('inf')\n",
    "        for i in range(1,len(listt)):\n",
    "            min_result=min(min_result,abs(listt[i]-listt[i-1])) if min_result!=0 else abs(listt[i]-listt[i-1])\n",
    "        return min_result\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        '''if not cur:\n",
    "            return\n",
    "        self.trverse(cur.left)\n",
    "        if self.pre:\n",
    "            self.result=min(self.result,cur.val-self.pre.val) if self.result!=0 else cur.val-self.pre.val\n",
    "        self.pre=cur\n",
    "        self.trverse(cur.right)'''\n",
    "    def getMinimumDifference(self, root: Optional[TreeNode]) -> int:\n",
    "        return self.trverse(root)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def getMinimumDifference(self, root: Optional[TreeNode]) -> int:\n",
    "\n",
    "        # 中序遍历为有序数组\n",
    "        stack = collections.deque()\n",
    "        pre = - 10 ** 6\n",
    "        res = 10 ** 7\n",
    "\n",
    "        stack.append(root.right)\n",
    "        stack.append(root.val)\n",
    "        stack.append(root.left)\n",
    "\n",
    "        while len(stack) > 0:\n",
    "\n",
    "            node = stack.pop()\n",
    "            if type(node) == int:\n",
    "                # 比较前一个元素\n",
    "                if node - pre < res:\n",
    "                    res = node - pre\n",
    "\n",
    "                pre = node\n",
    "\n",
    "            elif node:\n",
    "                stack.append(node.right)\n",
    "                stack.append(node.val)\n",
    "                stack.append(node.left)\n",
    "\n",
    "        return res\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
